package 回溯;

import java.util.LinkedList;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 被列覆盖的最多行数2397.java
 * @createTime 2023年08月31日 11:26:00
 */
public class 被列覆盖的最多行数2397 {

	public static void main(String[] args) {
		maximumRows(new int[][]{{0,0,0},{1,0,1},{0,1,1},{0,0,1}},2);
	}

	static int max = 0;
	static LinkedList<Integer> list = new LinkedList<>();

	public static int maximumRows(int[][] matrix, int numSelect) {
		backTrace(matrix, numSelect, 0, new boolean[matrix[0].length], matrix[0].length, 0);
		return max;
	}

	public static void backTrace(int[][] matrix, int numSelect, int curSelect, boolean[] used, int column, int curColumn) {
		//结束条件选择数量达到了
		if (curSelect == numSelect) {
			//计算最大值
			int temp = cal(matrix);
			max = Math.max(temp, max);
			return;
		}
		//列遍历
		for (int i = curColumn; i < column; i++) {
			//当前列已经被选择了
			if (used[i]) {
				continue;
			}
			//选择当前列
			list.addLast(i);
			used[i] = true;
			curSelect+=1;
			backTrace(matrix, numSelect, curSelect, used, column, i + 1);
			curSelect-=1;
			list.removeLast();
			used[i] = false;
		}

	}

	public static int cal(int[][] matrix) {
		int num = 0;
		//先找到1的位置
		for (int i = 0; i < matrix.length; i++) {
			boolean isCover = true;
			for (int j = 0; j < matrix[i].length; j++) {
				if (matrix[i][j] == 1 && !list.contains(j)) {
					isCover = false;
					break;
				}
			}
			if (isCover) {
				num += 1;
			}
		}
		return num;
	}
}
